package com.kuang.linkedlist;

/*给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。*/


/**
 * @author kjx
 */
public class DetectCycle {

    //还是快慢指针，稍微拓展了一下罢了
    //但是这个拓展使这个题目变难了很多很多很多，需要去找数学规律，运用追击问题相对运动画个图去模拟一下，其实是能发现规律的；
    //但是转换为代码又很麻烦，总之，不好搞......不如直接记录hash表，速度还更快
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fastPtr = head;
        ListNode slowPtr = head;
        boolean loopExists = false;
        while (fastPtr.next != null && fastPtr.next.next != null) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
            if (fastPtr == slowPtr) {
                loopExists = true;
                break;
            }
        }
        if (loopExists) {
            slowPtr = head;
            while (slowPtr != fastPtr) {
                slowPtr = slowPtr.next;
                fastPtr = fastPtr.next;
            }
            return slowPtr;
        }
        return null;
    }
}
